﻿#include"SList.h"
//打印链表
//细节1：限制条件 2：地址不连续，不要使用自增自减，应该使用赋值语句找到下一个节点
void SLTPrint(SLTNode* phead)//效果，1->2->3->...->NULL
{
	SLTNode* pcur = phead;
	while (pcur != NULL)//如果我写成pcur->next!=NULL的话，把下面的那句代码移上来，会导致最后一个节点的数据遍历不到,具体的话自己画图来理解

	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//创建节点并完成初始化
//细节1：这里需要返回他的地址，提供给后面代码使用2：判断空间是否开辟成功
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//这里不要再写structure了，因为我已经重定义了，否则就是 struct struct ListNode
	if (newnode == NULL)
	{//开辟不成功
		perror("malloc failed!");
		exit(1);
	}
	//开辟成功+初始化
	newnode->data = x;
	newnode->next = NULL;//不赋值的话现在就就是野指针，需要NULL去管理野指针
	return newnode;//因为我要插入的是节点，而不是整形数据，所以必须返回节点的地址
}
//链表尾插数据
//细节：这里需要用到二级指针，对形参的改变需要影响实参
//如果这样写，传值调用(void SLTPushBack(SLTNode* phead, SLTDataType x))
//出了函数过后，phead变量被销毁，只有对形参改变，而plist实参还是NULL并没有改变，打印的结果就只有NULL了
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = SLTBuyNode(x);
	//如果链表为空，phead就直接指向newnode，此时newnode是首节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//链表不为空，找尾结点，将尾结点和新节点连接起来
		SLTNode* ptail = *pphead;//这里为什么要有这条赋值语句？
		//因为*pphead==plist,若用*pphead去遍历,导致plist跟着改变,打印时传的是plist,导致打印的时候找不到头节点
		while (ptail->next)//等价于ptail->next != NULL
		{
			ptail = ptail->next;
		}
		//出循环代表ptail此时是NULL,将其赋值为下一个节点的地址
		ptail->next = newnode;
	}
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//防止传过来的是一个NULL
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;//头结点的next指向下一个节点的地址
	*pphead = newnode;//头结点往前去一个
}
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)//在这里,->优先级比*高，所以要加一个()
	{
		//此时链表中还有一个节点，prev不可能在往前，因为初始值为NULL，不能够对prev指针访问操作，不能对空指针解引用
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//此时链表中的节点>1个，能够找到prev，此时prev不为NULL
		SLTNode* prev = NULL;
		SLTNode* ptail = *pphead;
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev ptail
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur != NULL)//同SLTPrint一样这样写为了能够遍历到所有节点中的元素，如写为pcur->next!=NULL,最后一个节点数据访问不到
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//未找到
	return NULL;
}
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && pos);
	if (pos==*pphead)//(*pphead)->next == NULL
	{
		//头插，此时只有一个节点，找不到pos，prev死循环，这种情况单独讨论
		SLTPushFront(pphead, x);
	}
	else
	{
		//>一个节点，此时可以找到prev
		//pos在头结点之后--->找pos前驱节点
		SLTNode* newnode = SLTBuyNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)//如果此时只有一个节点，prev会陷入死循环，因为开始prev==pos，prev在向后走，找不到pos，这种情况单独讨论
		{
			prev = prev->next;
		}
		//在这里先处理左边的节点，或先处理右边的节点最后的效果是一样的，为了统一下方，都先处理右方的节点
		newnode->next = pos;
		prev->next = newnode;
	}
}
//在指定位置之后插⼊数据（这种不可能是头插了）
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	//这里与上一个方法区别，这里必须先处理右边的节点，如果先处理左边的节点，在处理右边时此时指向的是newnode，右边的节点就找不到了
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		//此时只有一个节点，头删
		SLTPopFront(pphead);
	}
	else
	{
		//此时节点数>1，可以找到prev，进而将pos之前的节点与之后的节点联系起来
		SLTNode* prev = *pphead;
		while (prev->next != pos)//这里只要找到pos即可，是prev在pos的前面一个
		{
			prev = prev->next;
		}
		//prev pos pos->next
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);//要有数据可删，pos下一个数据也可删
	SLTNode* del = pos->next;
	//pos del del->next
	pos->next = del->next;
	free(del);
	del = NULL;
}

//销毁链表
//细节：从后删的话，删除的上一个节点就找不到了，所以最好从前往后删，代码跟简洁
void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* pcur = *pphead;
	while (pcur!=NULL)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}
